package com.wwy.arithmetic.suanfa;

import com.wwy.arithmetic.suanfa.entry.TreeNode;

import java.util.*;

/**
 * 二叉树的前序遍历
 * 1
 * 2  3
 * 4  5 6  7
 */
public class TreeQianXuBianLi {

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        treeNode1.setLeft(treeNode2);
        treeNode1.setRight(treeNode3);
        treeNode2.setLeft(treeNode4);
        treeNode2.setRight(treeNode5);
        treeNode3.setLeft(treeNode6);
        treeNode3.setRight(treeNode7);
        List<Integer> numbers = getStackNum(treeNode1, new ArrayList<>());
        for (Integer number : numbers) {
            System.out.println("number = " + number);
        }
    }

    /**
     * *        1
     * *      2  3
     * *    4  5 6  7
     *
     * @param treeNode
     * @param list
     * @return
     */

    static List<Integer> getNumbers(TreeNode treeNode, List<Integer> list) {
        if (treeNode == null) {
            return list;
        }
        list.add(treeNode.getVal());
        getNumbers(treeNode.getLeft(), list);
        getNumbers(treeNode.getRight(), list);
        return list;
    }

    /**
     * 使用栈
     */

    static List<Integer> getStackNum(TreeNode treeNode, List<Integer> list) {
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        while (!stack.isEmpty() || treeNode != null) {
            while (treeNode != null) {
                list.add(treeNode.getVal());
                stack.push(treeNode);
                treeNode = treeNode.getLeft();
            }
            treeNode = stack.pop();
            treeNode = treeNode.getRight();
        }
        return list;
    }
}
